# Copyright 2013, Michael H. Goldwasser
#
# Developed for use with the book:
#
#    Data Structures and Algorithms in Python
#    Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
#    John Wiley & Sons, 2013
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

from .map_base import MapBase


class UnsortedTableMap(MapBase):
	"""Map implementation using an unordered list."""

	def __init__(self):
		"""Create an empty map."""
		self._table = []  # list of _Item's

	def __getitem__(self, k):
		"""Return value associated with key k (raise KeyError if not found)."""
		for item in self._table:
			if k == item._key:
				return item._value
		raise KeyError('Key Error: ' + repr(k))

	def __setitem__(self, k, v):
		"""Assign value v to key k, overwriting existing value if present."""
		for item in self._table:
			if k == item._key:  # Found a match:
				item._value = v  # reassign value
				return  # and quit
		# did not find match for key
		self._table.append(self._Item(k, v))

	def __delitem__(self, k):
		"""Remove item associated with key k (raise KeyError if not found)."""
		for j in range(len(self._table)):
			if k == self._table[j]._key:  # Found a match:
				self._table.pop(j)  # remove item
				return  # and quit
		raise KeyError('Key Error: ' + repr(k))

	def __len__(self):
		"""Return number of items in the map."""
		return len(self._table)

	def __iter__(self):
		"""Generate iteration of the map's keys."""
		for item in self._table:
			yield item._key  # yield the KEY
